#include <iostream>

using namespace std;

typedef long long dint;
typedef pair<int, int> solu;

solu exGCD(int a, int b) {
	if (b == 0) {
		return solu(1, 0);
	}
	solu t = exGCD(b, a % b);
	return solu(t.second, t.first - a / b * t.second);
}

int main() {
	dint a, b;
	cin >> a >> b;
	solu s = exGCD(a, b);
	dint ans = s.first % b;
	if (ans < 0) {
		ans += b;
	}
	cout << ans << endl;
}
